#pragma once 
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;

template<class T>
struct Greater 
{
  bool operator()(const T& left,const T& right)
  {
    return left>right;
  }
};
template<class T>
struct Less
{
  bool operator()(const T& left,const T& right)
  {
    return left<right;
  }
};

template<class T,class Compare=Less<T> >
class Heap
{
public:
  Heap()
  {}
  //---------------------建堆-----------------------------
  Heap(const T* arr,size_t size)
  {
    //1.将所有元素放入堆中
    for(size_t i=0;i<size;i++)
    {
      _arr.push_back(arr[i]);
    }
    //2.从最后一个非叶子节点开始向下调整堆
    int index=(size-2)/2;
    while(index>=0)
    {
      AdjustDown(index);
      index--;
    }
  }
  //--------------------向堆中插入元素---------------------
  void Push(const T& data)
  {
    _arr.push_back(data);
    AdjustUp(_arr.size()-1);
    
  }
  //--------------------从堆中删除元素---------------------
  void Pop()
  {
    assert(_arr.size());
    swap(_arr[0],_arr[_arr.size()-1]);
    _arr.pop_back();
    AdjustDown(0);
  }
  //-------------------取堆顶元素---------------------------
  T& Top()
  {
    assert(_arr.size());
    return _arr[0];
  }
  //-------------------对堆判空----------------------------
  bool Empty()
  {
    return _arr.empty();
  }
  //-------------------求堆中元素个数----------------------
  size_t Size()
  {
    return _arr.size();
  }
  //-------------------向下调整-----------------------------
  void AdjustDown(int parent)
  {
    int child=parent*2+1;
    Compare cmp;
    while(child<_arr.size())
    {
      //找出左右孩子中较小的结点
      if(child+1<_arr.size()&&cmp(_arr[child+1],_arr[child]))
      {
        child+=1;
      }
      //若孩子结点小于其父节点即交换，否则说明已经为最小堆，退出
      if(cmp(_arr[child],_arr[parent]))
      {
        swap(_arr[child],_arr[parent]);
        parent=child;
        child=child*2+1;
      }
      else 
      {
        break;
      }
    }
  }
  //--------------------向上调整-----------------------------
  void AdjustUp(int child)
  {
    int parent=(child-1)/2;
    Compare cmp;
    while(parent>=0)
    {
      if(cmp(_arr[child],_arr[parent]))
      {
        swap(_arr[child],_arr[parent]);
        child=parent;
        parent=(child-1)/2;
      }
      else 
      {
        break;
      }
    }
  }
  //---------------------打印堆中元素------------------------
  void Print()
  {
    assert(_arr.size()>0);
    for(int i=0;i<_arr.size();i++)
    {
      cout<<_arr[i]<<" ";
    }
    cout<<endl;
  }
private:
  vector<T> _arr;
};


///////////////////////////////////////////////////////
// 测试堆
///////////////////////////////////////////////////////
void TestHeap()
{
  int a[6]={3,9,0,4,2,7};
  Heap<int> heap(a,sizeof(a)/sizeof(a[0]));
  heap.Print();

  cout<<"Top:"<<heap.Top()<<endl;
  heap.Pop();
  heap.Print();
  heap.Push(1);
  heap.Print();
  
}



